The advantages of the wavelet transform over conventional transforms, such as the Fourier transform, are now well recognized. In many application areas, the wavelet transform is more efficient at representing signal features that are localized in both time and frequency. Over the past 15 years, wavelet analysis has become a standard technique in such diverse areas as geophysics, meteorology, audio signal processing, and image compression. Significantly, the 2-D biorthogonal discrete wavelet transform (DWT) has been adopted in the recently established the new JPEG-2000 still image compression standard.
The classical DWT can be calculated using an approach known as Mallat's tree algorithm. Here, the lower resolution wavelet coefficients of each DWT stage are calculated recursively according to the following equations:
                              c                                    j              -              1                        ,            k                          =                              ∑            m                    ⁢                                    c                              j                ,                m                                      ·                          h              ⁡                              [                                  m                  -                                      2                    ⁢                    k                                                  ]                                                                        (        1        )                                          d                                    j              -              1                        ,            k                          =                              ∑            m                    ⁢                                    c                              j                ,                m                                      ·                          g              ⁡                              [                                  m                  -                                      2                    ⁢                    k                                                  ]                                                                        (        2        )            where                cp,q is the qth lowpass coefficient at the pth resolution,        dp,q is the qth highpass coefficient at the pth resolution,        h is the lowpass wavelet filter corresponding to the mother wavelet, and        g is the highpass wavelet filter corresponding to the mother wavelet,        
The corresponding tree structure for a two-level DWT is illustrated in FIG. 1. As shown in FIG. 1, the forward transform is computed using a series of high and low pass filters, denoted by g(−n) and h(−n), respectively, that operate on an input cj at increasing resolutions along the dimension of the sample index n. The decimated (i.e., down-sampled by a factor of two using decimators down, ↓2) output of the high pass filters at different stages (dj−1, dj−2, . . . ) captures the detail information at different resolutions. The decimated output of each low pass filter e.g. (cj−1) is processed recursively by the low and high pass filters of the next stage to obtain cj−2 and dj−2. Finally, the decimated output of the low pass filter of the last stage corresponds to the low frequency content of the original signal at the lowest considered resolution. In Mallat's algorithm, the inverse transform is calculated using a reverse tree algorithm that repeatedly filters and interleaves the various streams of transform coefficients back into a single reconstructed data sequence.
The structure of the corresponding separable 2-D DWT algorithm is shown in FIG. 2, where G and H represents the lowpass and highpass subband filters, respectively. The input image is first decomposed horizontally; the resulting outputs are then decomposed vertically into four subbands usually denoted by LL, LH, HL, and HH. The LL subband can then be further decomposed in the same way.
In 1994, Sweldens proposed a more efficient way of constructing the biorthogonal wavelet bases, called the lifting scheme. Concurrently, similar ideas were also proposed by others. The basic structure of the lifting scheme is shown in FIG. 3. The input signal Sj,k is first split into even and odd samples. The detail (i.e., high frequency) coefficients dj−l,k of the signal are then generated by subtracting the output of a prediction function P of the odd samples from the even samples. The smooth coefficients (the low frequency components) are produced by adding the odd samples to the output of an update function U of the details. The computation of either the detail or smooth coefficients is called a lifting step.
Daubechies and Sweldens showed that every FIR wavelet or filter bank can be factored into a cascade of lifting steps, that is, it can be represented as a finite product of upper and lower triangular matrices and a diagonal normalization matrix. The high-pass filter g(z) and low-pass filter h(z) in Equations 1 and 2 can thus be rewritten as:
                              g          ⁡                      (            z            )                          =                              ∑                          i              =              0                                      J              -              1                                ⁢                                    g              i                        ⁡                          (              z              )                                                          (        3        )                                          h          ⁡                      (            z            )                          =                              ∑                          i              =              0                                      J              -              1                                ⁢                                    h              i                        ⁡                          (              z              )                                                          (        4        )            where J is the filter length. We can split the high-pass and low-pass filters into even and odd parts:g(z)=ge(z2)+z−1go(z2)  (5)h(z)=he(z2)+z−1ho(z2)  (6)The filters can also be expressed as a polyphase matrix as follows:
                              P          ⁡                      (            z            )                          =                  [                                                                                          h                    e                                    ⁡                                      (                    z                    )                                                                                                                    g                    e                                    ⁡                                      (                    z                    )                                                                                                                                            h                    o                                    ⁡                                      (                    z                    )                                                                                                                    g                    o                                    ⁡                                      (                    z                    )                                                                                ]                                    (        7        )            Using the Euclidean algorithrn, which recursively finds the greatest common divisors of the even and odd parts of the original filters, the forward transform polyphase matrix {tilde over (P)}(z) can be factored into lifting steps as follows:
                                                                                                              P                    ~                                    ⁡                                      (                    z                    )                                                  =                                                      ∏                                          i                      =                      1                                        m                                    ⁢                                                                                    [                                                                                                            1                                                                                      0                                                                                                                                                                          -                                                                                                      s                                    i                                                                    ⁡                                                                      (                                                                          z                                                                              -                                        1                                                                                                              )                                                                                                                                                                                      1                                                                                                      ]                                            ⁡                                              [                                                                                                            1                                                                                                                      -                                                                                                      t                                    i                                                                    ⁡                                                                      (                                                                          z                                                                              -                                        1                                                                                                              )                                                                                                                                                                                                                                          0                                                                                      1                                                                                                      ]                                                              ⁡                                          [                                                                                                                                  1                              /                              K                                                                                                            0                                                                                                                                0                                                                                K                                                                                              ]                                                                                  ,                                                          m              ≤                              K                .                                                                        (        8        )            where si(z) and ti(z) are Laurent polynomials corresponding to the update and prediction steps, respectively, and K is a non-zero constant. The inverse DWT is described by the following synthesis polyphase matrix:
                              P          ⁡                      (            z            )                          =                              ∏                          i              =              1                        m                    ⁢                                                    [                                                                            1                                                                                                                s                          i                                                ⁡                                                  (                          z                          )                                                                                                                                                0                                                              1                                                                      ]                            ⁡                              [                                                                            1                                                              0                                                                                                                                                    t                          i                                                ⁡                                                  (                          z                          )                                                                                                            1                                                                      ]                                      ⁡                          [                                                                    K                                                        0                                                                                        0                                                                              1                      /                      K                                                                                  ]                                                          (        9        )            
As an example, the low-pass and high-pass filters corresponding to the Daubechies 4-tap wavelet can be expressed as:{tilde over (h)}(z)=ho+h1z−1+h2z−2+h3z−3 {tilde over (g)}(z)=−h3z2+h2z1−h1+h0z−1,  (10)where
            h      0        =                  1        +                  3                            4        ⁢                  2                      ,            h      1        =                  3        +                  3                            4        ⁢                  2                      ,            h      2        =                  3        -                  3                            4        ⁢                  2                      ,            h      3        =                  1        -                  3                            4        ⁢                  2                    Following the above procedure, we can factor the analysis polyphase matrix of the Daubechies-4 wavelet filter as:
                                                                                          P                  ~                                ⁡                                  (                  z                  )                                            =                                                [                                                                                    1                                                                                              -                                                      3                                                                                                                                                              0                                                                    1                                                                              ]                                ⁡                                  [                                                                                    1                                                                    0                                                                                                                                                                                                3                                                        4                                                    +                                                                                                                                                      3                                                                -                                2                                                            4                                                        ⁢                                                          z                                                              -                                1                                                                                                                                                                                1                                                                              ]                                                                                                                                                    ⁢                                                [                                                                                    1                                                                    z                                                                                                            0                                                                    1                                                                              ]                                ⁡                                  [                                                                                                                                                                        3                                                        +                            1                                                                                2                                                                                                                      0                                                                                                            0                                                                                                                          (                                                                                                                            3                                                                +                                1                                                                                            2                                                                                      )                                                                                -                            1                                                                                                                                ]                                                                                        (        11        )            The corresponding synthesis polyphase matrix can be factored as:
                                                                        P                ⁡                                  (                  z                  )                                            =                            ⁢                                                [                                                                                                                                          (                                                                                                                            3                                                                +                                1                                                                                            2                                                                                      )                                                                                -                            1                                                                                                                      0                                                                                                            0                                                                                                                                                        3                                                        +                            1                                                                                2                                                                                                                                ]                                ⁡                                  [                                                                                    1                                                                                              -                          z                                                                                                                                    0                                                                    1                                                                              ]                                                                                                                      ⁢                                                [                                                                                    1                                                                    0                                                                                                                                                                  -                                                                                          3                                                            4                                                                                -                                                                                                                                                      3                                                                -                                2                                                            4                                                        ⁢                                                          z                                                              -                                1                                                                                                                                                                                1                                                                              ]                                ⁡                                  [                                                                                    1                                                                                              3                                                                                                                                    0                                                                    1                                                                              ]                                                                                        (        12        )            Similarly, the 9/7 analysis wavelet filter can be factored as:
                                                                                          P                  ~                                ⁡                                  (                  z                  )                                            =                            ⁢                                                                    [                                                                                            1                                                                                                      α                            ⁡                                                          (                                                              1                                +                                                                  z                                                                      -                                    1                                                                                                                              )                                                                                                                                                                            0                                                                          1                                                                                      ]                                    ⁡                                      [                                                                                            1                                                                          0                                                                                                                                                  β                            ⁡                                                          (                                                              1                                +                                z                                                            )                                                                                                                                1                                                                                      ]                                                  ⁡                                  [                                                                                    1                                                                                              γ                          ⁡                                                      (                                                          1                              +                                                              z                                                                  -                                  1                                                                                                                      )                                                                                                                                                              0                                                                    1                                                                              ]                                                                                                                      ⁢                                                [                                                                                    1                                                                    0                                                                                                                                      δ                          ⁡                                                      (                                                          1                              +                              z                                                        )                                                                                                                      1                                                                              ]                                ⁡                                  [                                                                                    ζ                                                                    0                                                                                                            0                                                                                              ζ                                                      -                            1                                                                                                                                ]                                                                                        (        13        )            The corresponding synthesis wavelet filter is factored as:
                                                                        P                ⁡                                  (                  z                  )                                            =                            ⁢                                                                    [                                                                                                                        ζ                                                          -                              1                                                                                                                                0                                                                                                                      0                                                                          ζ                                                                                      ]                                    ⁡                                      [                                                                                            1                                                                                                      -                                                          δ                              ⁡                                                              (                                                                  1                                  +                                  z                                                                )                                                                                                                                                                                                          0                                                                          1                                                                                      ]                                                  ⁡                                  [                                                                                    1                                                                    0                                                                                                                                      -                                                      γ                            ⁡                                                          (                                                              1                                +                                                                  z                                                                      -                                    1                                                                                                                              )                                                                                                                                                  1                                                                              ]                                                                                                                      ⁢                                                [                                                                                    1                                                                                              -                                                      β                            ⁡                                                          (                                                              1                                +                                z                                                            )                                                                                                                                                                                          0                                                                    1                                                                              ]                                ⁡                                  [                                                                                    1                                                                    0                                                                                                                                      -                                                      α                            ⁡                                                          (                                                              1                                +                                                                  z                                                                      -                                    1                                                                                                                              )                                                                                                                                                  1                                                                              ]                                                                                        (        14        )            where the values of α, β, γ, δ, and ζ are shown in FIG. 8. The computational cost of calculating two Daub-4 DWT coefficients using Equation 11 is nine operations (five multiplications and four additions). On the other hand, Mallat's algorithm needs fourteen arithmetic operations (eight multiplications and six additions) according to Equation 10. In other words, the lifting steps provide 35% speed up for Daub-4 DWT calculation. For longer FIR wavelet filters, the speed up can be up to 50%, which is a significant improvement for real-time applications.